import java.awt.image.Kernel;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
         TreeNode node = new TreeNode(key);
         if(this.root == null){
             this.root = node ;
             return  true ;
         }
         if(search(key) != null){
             return false ;
         }
        TreeNode cur = this.root ;
         TreeNode parent = null ;
         while(cur != null){
             if(key > cur.key){
                 parent = cur ;
                 cur = cur.right ;
             }else{
                 parent = cur ;
                 cur = cur.left ;
             }
         }
         if(key > parent.key){
             parent.right = node ;
         }else{
             parent.left = node ;
         }
        return true;
    }
    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur = this.root ;
        while(cur != null){
            if(cur.key == key){
                return cur;
            }else if(key > cur.key){
               cur = cur.right ;
            }else{
                cur = cur.left ;
            }
        }
        return null;
    }
    //删除key的值
    public boolean remove(int key) {
        if(search(key) == null){
            return false ;
        }
         TreeNode cur = this.root ;
         TreeNode parent = null ;
        while(cur != null){
            if(key > cur.key){
                parent = cur ;
                cur = cur.right ;
            }else if(key < cur.key){
                parent = cur ;
                cur = cur.left ;
            }else{
                break ;
            }
        }
        if(cur.left == null && cur.right == null){
             if(cur == root){
                 this.root = null ;
             }else{
                 if(cur == parent.left){
                     parent.left = null ;
                 }else{
                     parent.right = null ;
                 }
             }
        }else if(cur.left == null && cur.right != null){
            if(cur == root){
                root = cur.right ;
            }else{
                if(cur == parent.left){
                    parent.left = cur.right ;
                }else{
                    parent.right = cur.right ;
                }

            }
        }else if(cur.left != null && cur.right == null){
            if(cur == root){
                root = cur.left ;
            }else{
                if(cur == parent.left){
                    parent.left = cur.left ;
                }else{
                    parent.right = cur.left ;
                }
            }
        }else {
            TreeNode rightMax = cur.left ;
            TreeNode maxParent = cur ;
            while(rightMax.right != null){
                maxParent = rightMax ;
                rightMax = rightMax.right;
            }

            cur.key = rightMax.key;
            if(maxParent.left == rightMax){
                maxParent.left = rightMax.left;
            }else{
                maxParent.right = rightMax.left;
            }
        }


        return true;
    }


}